package com.mamingchao.basic.swardToOffer.one;

import org.springframework.util.StopWatch;
import org.springframework.util.StringUtils;

import java.util.Arrays;
import java.util.Hashtable;

/**
 * ??????????
 * 1????????????????????????
 * 2??hash ??????
 *
 * ?????? ???????????????????????? ??hash???
 *
 * ???????hash ??? key? value??? value?? ???????index
 * key    value
 * 15       0
 * 11       1
 * 7        2
 * 2        3
 * 3        4
 * 4        5
 * 5        6
 *
 * ??? ?? target(9) - key(15)?? ??? target-key == key1, key1??? hash??key?????? key ??key1???? ??
 * ???  target(9) - key(15) ????(key1)?????? hash???????target(9) - key(11)
 * ????????????? 9-15 = -6??
 * Created by mlamp on 2024/6/27.
 */
public class FindTwoNumsSumEqualstarget {

    public static void main(String[] args) {
        final int target = 9;

        int[] arr = {15,11,7,2,3,4};

        System.out.println(Arrays.toString(getTwoNums(arr, target)));


    }

    private static int[] getTwoNums(int[] arr, int target) {

        StopWatch stopWatch = new StopWatch();
        stopWatch.start("????????????");
        int[] result = new int[2];

        Hashtable<Integer,Integer> table = new Hashtable <>();

        // ?????????????????hashtable??key ?? ????????value????index
        for (int i = 0; i < arr.length; i++) {
            table.put(arr[i],i);
        }

        for (int i = 0; i < arr.length; i++) {
            // target - ?????? == ??????
            int parternerKey = target - arr[i];
            // ?????????index ? i


            // ??? hash?????? ?? ?????????? ???? ?????????? ????????????????????????????
            if (table.containsKey(parternerKey) ) {
                //????????????index
                int parternerIndex = table.get(parternerKey);
                if (i !=  parternerIndex) {
                    result[0] = i;
                    result[1] = parternerIndex;
                }
            } else {
                continue;
            }
        }
        stopWatch.stop();

        System.out.println(String.format("????-{}", stopWatch ) );
        System.out.println("????" + stopWatch);

        return result;
    }
}
